Convolutional codes are often used in digital communication systems to protect transmitted information from error. At the transmitter, an outgoing code vector may be described using a trellis diagram whose complexity is determined by the constraint length of the encoder. Although computational complexity increases with increasing constraint length, the robustness of the coding also increases with constraint length.
At the receiver, a practical soft-decision decoder, such as a Viterbi decoder, uses a trellis structure to perform an optimum search for the maximum likelihood transmitted code vector. The Viterbi algorithm, however, is computationally complex, and its complexity increases exponentially with increasing constraint length. This essentially means that a Viterbi decoder requires a significant amount of current and a tremendous millions of instructions per second (MIPS) capability for processing convolutional codes with large constraint lengths.
Vocoders for various communications systems, such as Direct Sequence Code Division Multiple Access (DS-CDMA) standard IS-95 and Global System for Mobile Communications (GSM), have such large constraint lengths. For example, the GSM half-rate constraint length K=7 and the IS-95 constraint length K=9.
Another disadvantage of Viterbi decoders is that a fixed number of computations must be performed for each code vector, irrespective of the actual number of errors that occurred during transmission. Thus, a Viterbi decoder processes a received signal having few transmission errors or no errors at all using the same number of computations as a received signal having many errors. There is a need for a soft-decision decoder that has a reduced current and MIPS processing requirement for convolutional codes with large constraint lengths and communication channels with low error rates.